package com.lc.lc494;

public class Main {

}

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i ++) {
            sum += nums[i];
        }

        int tmp = sum - target;

        if (tmp < 0 || tmp % 2 == 1) {
            return 0;
        }

        int neg = tmp / 2;

        int[] f = new int[neg + 1];
        f[0] = 1;
        for (int i = 0; i < n; i ++) {
            for (int j = neg; j >= nums[i]; j --) {
                f[j] += f[j - nums[i]];
            }
        }
        return f[neg];
    }
}
